package bank;

import java.util.*;

public class _47PermuteUnique {
    //  该算法运行效率极低，因为哈希表底层运用红黑树，查重耗时较长
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        backtrack(res,nums,new ArrayList<Integer>(),new HashSet<Integer>(),0);
        return new ArrayList<>(res);
    }

    private static void backtrack(Set<List<Integer>> res, int[] nums, ArrayList<Integer> list, HashSet<Integer> hashSet, int index) {
        if (index == nums.length){
            List<Integer> list0 = new ArrayList<>(list);
            res.add(list0);
        }
        for (int i = 0;i < nums.length;i++){
            //  该问题的难点是如何查重
            //  查重条件：如果当前该添加进list的元素在上一步刚刚被撤销选择，则判定为重复项！！！
            //  可以在一开始就对nums数组中的元素进行排序
            if (!hashSet.contains(i)){
                hashSet.add(i);
                list.add(nums[i]);
                backtrack(res,nums,list,hashSet,index+1);
                hashSet.remove(i);
                list.remove(list.size()-1);
            }
        }
    }
}
